The present invention relates to a high-speed determining unit having priority and arbitration useful with computers, fast packet switches and other communication switches, and other systems.
This application is a continuation-in-part of the above-identified cross-referenced application Ser. No. 07/602,409. In computer, communication, and other electronic systems, the condition often arises where a plurality of competing requests are made for access to one or more resources, but the resources cannot during any given time period, accommodate all of the requests. When such a condition arises, there is a need to determine which one or more of the requests is to be honored.
The algorithms for, and corresponding methods of and apparatus for, determining which one or more requests among a plurality of competing requests will be honored have been implemented in many ways. The determination of which request is to be honored is a matter of arbitrating between competing requests in accordance with an arbitration algorithm.
One example of an arbitration algorithm is a "first come first served" (FCFS) algorithm. Such a FCFS algorithm is useful in environments where the competing inputs are presented at different times. However, in synchronous systems where many requesting inputs occur during the same common time interval, the FCFS algorithm is not always satisfactory.
Another example of an arbitration algorithm is a "round robin" algorithm where the competing inputs are honored in a regular and sequential order. Such an algorithm is useful where the competing inputs are accorded equal weight, but the algorithm does not permit the competing inputs to be honored based upon a predetermined priority.
Algorithms exist in which some competing requests are accorded higher priority than others of the competing requests. With such priority algorithms, competing inputs of higher priority are honored before competing requests of lower priority.
While many algorithms exist for determining which one or more requests among a plurality of competing requests will be honored, embodiments of those algorithms in useful circuits have not always been satisfactory particularly when high-speed operation is required.
Accordingly, there is a need for improved methods and apparatus capable of high-speed operation for determining which one or more requests among a plurality of competing requests will be honored in a computer, communication or other system.